use std::cmp;
use std::collections::HashMap;

static mut CC : u32 = 0;

fn main() {
    let amount : i32 = 11;
    let mut coins : [i32; 3] = [2, 1, 5];
    coins.sort();
    coins.reverse();
    //let mut memo = HashMap::new();
    unsafe {
        println!("{} in {:?} = {} with {} times",
                 amount,
                 coins,
                 coin_exchange_simple(&coins, amount),
                 CC
        );
    }
}

/*
 * 最简单的算法
 */
fn coin_exchange_simple(coins : &[i32], x : i32) -> i32 {
    let mut cc = 0;
    let mut tc = x;
    for coin in coins {
        cc += tc / coin;
        tc = tc % coin;
    }
    cc
}

/**
 * 带备忘录的动态规划
 */
unsafe fn coin_exchange_with_memo (coins : &[i32], x : i32, memo : &mut HashMap<i32,i32>) -> i32 {
    if x == 0 {
        return 0;
    }
    if x < 0 {
        return -1;
    }
    if memo.contains_key(&x) {
        return memo[&x];
    }
    CC = CC + 1;
    let mut res = std::i32::MAX;
    for coin in coins {
        let subp = coin_exchange_with_memo ( coins,x - coin , memo);
        if subp == -1 {
            break; // 已经确保 coins 是有序序列，因此无需重复循环，直接跳出
        }
        res = cmp::min(res, 1 + subp);
    }
    if res < std::i32::MAX {
        memo.insert(x, res);
        res
    }
    else { -1 }
}

/**
 * 基本的动态规划
 */
unsafe fn coin_exchange(coins : &[i32], x : i32) -> i32 {
    CC = CC + 1;
    if x == 0 {
        return 0;
    }
    if x < 0 {
        return -1;
    }
    let mut res = std::i32::MAX;
    for coin in coins {
        let subp = coin_exchange ( coins,x - coin );
        if subp == -1 {
            continue;
        }
        res = cmp::min(res, 1 + subp);
    }
    if res != std::i32::MAX { res } else { -1 }
}
